//
//  SqQueueExt.hpp
//  DataStructure
//
//  Created by 舒磊明 on 2020/7/2.
//  Copyright © 2020 Shuleiming. All rights reserved.
//

#ifndef SqQueueExt_hpp
#define SqQueueExt_hpp

#include <stdio.h>
#include <stdlib.h>
#include "SqQueue.hpp"
#include "SqStack.hpp"

typedef int ElemType;

// 带有tag的队列
typedef struct {
    int tag;
    ElemType data[MAX_SIZE];
    int front, rare;
} TagQueue;

// tag队列入队
bool TagPush(TagQueue &Q, ElemType x);

// tag队列出队
bool TagPop(TagQueue &Q, ElemType &x);

// Q是队列，S是栈，将队列逆序
void QueueReverse(SqQueue &Q, SqStack &S);

// 栈的操作：Push,Pop,StackEmpty,StackOverflow
// 实现队列操作：EnQuqeue,DeQueue,QueueEmpty

/*
 1.初始化队列为空
 2.入队允许增加空间
 3.出队后，空间不减少
 4.出队和入队都为O(1)
 
 1)应该使用链式存储
 2)front和rare指向循环单链表的头结点
 队空：Q.front == Q.rare
 队满：Q.rare->next = Q.front
 3)O ---> O
   <------|
 4)入队：
 if (Q.rare->next == Q.front) { // 队满则增加结点
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = rare->next;
    rare->next = s;
 }
 rare = rare->next;
 出队：
 if (Q.rare == Q.front) return false; // 队空返回false
 x = Q.front.data;
 Q.front = Q.front->next;
 */

#endif /* SqQueueExt_hpp */
